As we know, a graph $G$ is formally defined as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.

  • Vertices (V) are the nodes or points in the graph, representing entities like cities or network devices.
  • Edges (E) are the connections or links between vertices, representing relationships or paths.
  • Graphs are commonly represented using an Adjacency List, where each vertex stores a list of its direct neighbors.
  • The Adjacency List is efficient for sparse graphs and is the primary representation used in most graph algorithms.
  • Alternatively, an Adjacency Matrix (a $V \times V$ grid) is better suited for dense graphs but uses more memory.
Adjacency List Representation (Python)

1# Adjacency List Representation (using a dictionary)
2# G = {
3#   vertex: [neighbor1, neighbor2, ...]
4# }
5
6graph = {
7    'A': ['B', 'C'],
8    'B': ['A', 'D'],
9    'C': ['A'],
10    'D': ['B']
11}